// 稳定的排序算法，最好平均最坏时间复杂度都是 O(nlogn)
// 分治思想，先分解后合并
#include <stdio.h>
#include <stdlib.h>

void sort(int arr[], int n);
void inSort(int arr[], int left, int right, int temp[]);
void merge(int arr[], int left, int mid, int right, int temp[]);

int main(int argc, const char* argv[]) {
	int arr[] = {9, 5, 2, 1, 6, 3, 4, 7, 8};
	int n = sizeof(arr)/sizeof(int);
	printf("%d\n", n);
	sort(arr, n);
	for (int i = 0; i < n; ++i) {
		fprintf(stdout, "%d ", arr[i]);
	}
	return 0;
}

void sort(int arr[], int n) {
	int temp[n];
	inSort(arr, 0, n-1, temp);
}

void inSort(int arr[], int left, int right, int temp[]) {
	if (left < right) {
		int mid = (left+right) / 2;
		inSort(arr, left, mid, temp);
		inSort(arr, mid+1, right, temp);
		merge(arr, left, mid, right, temp);
	}
}

void merge(int arr[], int left, int mid, int right, int temp[]) {
	int i = left;
	int j = mid + 1;
	int t = 0;
	while (i <= mid && j <= right) {
		if (arr[i]<=arr[j]) {
			temp[t++] = arr[i++];
		} else {
			temp[t++] = arr[j++];
		}
	}
	while (i <= mid) {
		temp[t++] = arr[i++];
	}
	while (j <= right) {
		temp[t++] = arr[j++];
	}
	t = 0;
	while (left <= right) {
		arr[left++] = temp[t++];
	}
}
